function Node(value=null, left=null, right=null) {
    this.value = value;
    this.left = left;
    this.right = right;
}

class BST{
    constructor(){
        this.root=null;
    }

    /**
     * 插入
     */
    insert(v){
        let node=new Node(v);
        
        if(this.root===null){
            this.root=node;
            return;
        }

        let iter=this.root;
        while(true){
            let parent=iter;
            if(v>iter.value){
                iter=iter.right;
                if(iter===null){
                    parent.right=node;
                    break;
                }
            }else{
                iter=iter.left;
                if(iter===null){
                    parent.left=node;
                    break;
                }
            }
        }
    }

    /** 中序遍历 */
    inorderPrintPartition(node){
        if(node===null){
            return;
        }
        this.inorderPrintPartition(node.left);
        console.log(node.value);
        this.inorderPrintPartition(node.right);
    }
    inorderPrint(){
        this.inorderPrintPartition(this.root);
    }

    /** 按层遍历 */
    BFS(){
        if(this.root==null){
            return;
        }
        let queue=[this.root];
        while(queue.length>0){
            let node=queue.shift();
            console.log(node.value);
            if(node.left!=null){
                queue.push(node.left);
            }
            if(node.right!=null){
                queue.push(node.right);
            }
        }
    }

    /** 将数组转为BST */
    arrayToBST(arr){
        arr.forEach(e => {
            this.insert(e);
        });
    }
}

/** test */
const bst=new BST();
arr=[56,22,81,10,30,77,92];
bst.arrayToBST(arr);
bst.BFS();
// bst.inorderPrint();